package codingforgreat.class03;
// 本题测试链接 : https://leetcode.com/problems/largest-1-bordered-square/
public class Class03_Largest1BorderedSquare {
    public int largest1BorderedSquare(int[][] grid) {
        if(grid==null || grid.length == 0){
            return 0;
        }
        if(grid.length == 1 && grid[0].length == 1){
            return grid[0][0] == 1 ? 1 : 0;
        }
        int[][] right = new int[grid.length][grid[0].length];
        int[][] down = new int[grid.length][grid[0].length];
        getRightAndDown(grid,right,down);
        int size = 1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                for (int k = Math.min(right[i][j],down[i][j]); k > 0 ; k--) {
                    if(hasSqu(i,j,k,right,down)){
                        size = Math.max(size,k*k);
                        continue;
                    }
                }
            }
        }
        return size;
    }
    public static boolean hasSqu(int i,int j,int k,int[][] right,int[][] down){
//        a:(i,j) b : (i,j + k) c : (i + k , j) d : (i + k,j + k )
        int n = right.length;
        int m = right[0].length;
        if((j + k <= m )&&(i + k <= n)){
//            if(down[i][j + k] >= k && right[i + k][j] >= k){
//                return true;
//            }
            if (right[i + k - 1][j] >= k
                    && down[i][j + k - 1] >= k) {
                return true;
            }
        }
        return false;
    }
    public static void getRightAndDown(int[][] m,int[][] right,int[][] down){
        int r = m.length;
        int c = m[0].length;
        if (m[r - 1][c - 1] == 1) {
            right[r - 1][c - 1] = 1;
            down[r - 1][c - 1] = 1;
        }

        for (int i = r - 2; i != -1; i--) {
            if (m[i][c - 1] == 1) {
                right[i][c - 1] = 1;
                down[i][c - 1] = down[i + 1][c - 1] + 1;
            }
        }
        for (int i = c - 2; i != -1; i--) {
            if (m[r - 1][i] == 1) {
                right[r - 1][i] = right[r - 1][i + 1] + 1;
                down[r - 1][i] = 1;
            }
        }
        for (int i = r - 2; i != -1; i--) {
            for (int j = c - 2; j != -1; j--) {
                if (m[i][j] == 1) {
                    right[i][j] = right[i][j + 1] + 1;
                    down[i][j] = down[i + 1][j] + 1;
                }
            }
        }
    }
}
